import java.util.*;

/**
 * Created With IntelliJ IDEA
 * Description:leetcode：136. 只出现一次的数字
 * <a href="https://leetcode.cn/problems/single-number/">...</a>
 * User: DELL
 * Data: 2023-02-15
 * Time: 23:21
 */

public class Solution {
    /**
     * 方法一；使用异或运算
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        //题目规定nums数组中至少有一个元素
        int tmp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            tmp ^= nums[i];
        }
        return tmp;
    }

    /**
     * 方法二：使用HashSet
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        Set<Integer> hashSet = new HashSet<>();
        hashSet.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                hashSet.remove(nums[i]);
            } else {
                hashSet.add(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(hashSet.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }
}
